class Solution{
public:
  vector<int> tmp;
  vector<vector<int>> res;

  vector<vector<int>> combinationSum(vector<int> &candidates, int target){

    dfs(candidates, target, 0);
    
    return res;

  }

  void dfs(vector<int> &candidates, int target, int start){

    if(target < 0)
      return;
    if(target == 0){
      res.push_back(tmp);
      return;
    }

    for(int i = start; i < candidates.size(); i++){
      tmp.push_back(candidates[i]);
      dfs(candidates, target - candidates[i], i);
      tmp.pop_back();
    }
  }

};